Week 0- Welcome to Algorithms, Part I

文章目录

1. 1. Week 0

Algorithms, Part I
by Kevin Wayne, Robert Sedgewick
2016-06-17 FRI :start

Week 0

COurse Introduction

What is this course?

• Intermediate-level survey course.

  Intermediate-level:中级别的

• Programming and problem solving, with application

• Algorithm: method for solving a problem.

• Data structure: method to store information

topic	data structures and algorithms
data types	stack,queue,bag(?),union-find(并查集的数据结构),priority queue(优先队列)
sorting	quicksort,mergesort*(归并排序)*,heapsort(堆排序)
searching	BST,red-black BST,hash table
graphs	BFS,DFS,Prim,Kruskal,Dijkstra
strings	radix sorts,tries,KMP,regexps,data compression
advanced	B-tree,suffix array*(后缀数组),maxflow(最大流增广路算法)*

1. Their impact is broad 影响 and far-reaching 深远

Internet.

Web search, packet routing, distributed file sharing, …

Biology. 生物学 Human genome project人类基因组计划,protein folding蛋白质折叠,….

Computers. Circuit layout电路设计,file system,compilkers,….

Computer graphics. Movies,video games,virtual relity,…

Security. Cell phones, e-commerce,voting machines,…

Multimedia. MP3,JPG,DivX,HDTV,face recognition,…

Social networks. Recommendations,news feeds,advertisements,…

Physics. N-body simulation,particle collision simuluations,…

2. Old roots, new opportunities

• Study of algorithms dates at least to Euclid. 欧几里得
• Formalized by Church and Turing in 1930s.
• Some important algorithms were discovered
  by undergraduates 大学生in a course like this!

3. To solve problems that could not otherwise be addressed
Ex. Network connectivity.[stay tuned]敬请期待

3. For intellectual stimulation

• Francis Sullivan:

  “For me, great algorithms are the poetryn.诗 of computation. Just like
  verse诗篇, they can be terse精练, allusive, dense, and even mysterious.
  But once unlocked, they cast a brilliant new light on some
  aspect of computing. ”

• Donald Knuth

  “An algorithm must be seen to be believed. ”

4. To become a proficient programmer.

Linus Torvalds (creator of Linux):

“ I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures
more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ”

• Niklaus Wirth:

  “Algorithms + Data Structures = Programs. ”

4.They may unlock the secrets of life and of the universe

Computational models计算模型 are replacing math models in scientific inquiry科学探索

formula:公式

/*

It’s an intermediate level survey course on algorithms.We’re going to concentrate on programming and problem solving in the

Welcome.I’m Bob SDedgewick,professor of computer science at Princetion.

princeton: 普林斯顿

*/